home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / pctchnqs / 1990 / number5 / l1.c < prev    next >
Text File  |  1990-09-29  |  5KB  |  124 lines
  1. /* Program to search through an array spanning a linked list of
  2.    variable-sized blocks for all entries with a specified ID number
  3.    and return the average of the values of all such entries. Each of
  4.    the variable-sized blocks may contain any number of data entries,
  5.    stored as an array of structures within the block.
  6. */
  7.  
  8. #include <stdio.h>
  9. #ifdef __TURBOC__
  10. #include <alloc.h>
  11. #else
  12. #include <malloc.h>
  13. #endif
  14.  
  15. void main(void);
  16. void exit(int);
  17. unsigned int FindIDAverage(unsigned int, struct BlockHeader *);
  18.  
  19. /* Structure that starts each variable-sized block */
  20. struct BlockHeader {
  21.    struct BlockHeader *NextBlock; /* pointer to next block, or NULL
  22.                                     if this is the last block in the
  23.                                     linked list */
  24.    unsigned int BlockCount;      /* the number of DataElement entries
  25.                                     in this variable-sized block */
  26. };
  27.  
  28. /* Structure that contains one element of the array we'll search */
  29. struct DataElement {
  30.    unsigned int ID;     /* ID # for array entry */
  31.    unsigned int Value;  /* value of array entry */
  32. };
  33.  
  34. void main(void) {
  35.    int i,j;
  36.    unsigned int IDToFind;
  37.    struct BlockHeader *BaseArrayBlockPointer,*WorkingBlockPointer;
  38.    struct DataElement *WorkingDataPointer;
  39.    struct BlockHeader **LastBlockPointer;
  40.  
  41.    printf("ID # for which to find average: ");
  42.    scanf("%d",&IDToFind);
  43.  
  44.    /* Build an array across 5 blocks, for testing */
  45.    /* Anchor the linked list to BaseArrayBlockPointer */
  46.    LastBlockPointer = &BaseArrayBlockPointer;
  47.    /* Create 5 blocks of varying sizes */
  48.    for (i = 1; i < 6; i++) {
  49.       /* Try to get memory for the next block */
  50.       if ((WorkingBlockPointer =
  51.             (struct BlockHeader *) malloc(sizeof(struct BlockHeader) +
  52.             sizeof(struct DataElement) * i * 10)) == NULL) {
  53.          exit(1);
  54.       }
  55.       /* Set the # of data elements in this block */
  56.       WorkingBlockPointer->BlockCount = i * 10;
  57.       /* Link the new block into the chain */
  58.       *LastBlockPointer = WorkingBlockPointer;
  59.       /* Point to the first data field */
  60.       WorkingDataPointer =
  61.             (struct DataElement *) ((char *)WorkingBlockPointer +
  62.             sizeof(struct BlockHeader));
  63.       /* Fill in the data fields with ID numbers and values */
  64.       for (j = 0; j < (i * 10); j++, WorkingDataPointer++) {
  65.          WorkingDataPointer->ID = j;
  66.          WorkingDataPointer->Value = i * 1000 + j;
  67.       }
  68.       /* Remember where to set the link from this block to the next */
  69.       LastBlockPointer = &WorkingBlockPointer->NextBlock;
  70.    }
  71.    /* Set the last block's "next block" pointer to NULL to indicate
  72.       that there are no more blocks */
  73.    WorkingBlockPointer->NextBlock = NULL;
  74.  
  75.    printf("Average of all elements with ID %d: %u\n",
  76.          IDToFind, FindIDAverage(IDToFind, BaseArrayBlockPointer));
  77.    exit(0);
  78. }
  79.  
  80. /* Searches through the array of DataElement entries spanning the
  81.    linked list of variable-sized blocks starting with the block
  82.    pointed to by BlockPointer for all entries with IDs matching
  83.    SearchedForID, and returns the average value of those entries. If
  84.    no matches are found, zero is returned */
  85. unsigned int FindIDAverage(unsigned int SearchedForID,
  86.       struct BlockHeader *BlockPointer)
  87. {
  88.    struct DataElement *DataPointer;
  89.    unsigned int IDMatchSum;
  90.    unsigned int IDMatchCount;
  91.    unsigned int WorkingBlockCount;
  92.  
  93.    IDMatchCount = IDMatchSum = 0;
  94.    /* Search through all of the linked blocks until the last block
  95.       (marked with a NULL pointer to the next block) has been
  96.       searched */
  97.    do {
  98.       /* Point to the first DataElement entry within this block */
  99.       DataPointer =
  100.             (struct DataElement *) ((char *)BlockPointer +
  101.             sizeof(struct BlockHeader));
  102.       /* Search through all the DataElement entries within this block
  103.          and accumulate data from all that match the desired ID */
  104.       for (WorkingBlockCount=0;
  105.             WorkingBlockCount<BlockPointer->BlockCount;
  106.             WorkingBlockCount++, DataPointer++) {
  107.          /* If the ID matches, add in the value and increment the
  108.             match counter */
  109.          if (DataPointer->ID == SearchedForID) {
  110.             IDMatchCount++;
  111.             IDMatchSum += DataPointer->Value;
  112.          }
  113.       }
  114.    /* Point to the next block, and continue so long as that pointer
  115.       isn't NULL */
  116.    } while ((BlockPointer = BlockPointer->NextBlock) != NULL);
  117.  
  118.    /* Calculate the average of all matches */
  119.    if (IDMatchCount == 0)
  120.       return(0);            /* avoid division by 0 */
  121.    else
  122.       return(IDMatchSum / IDMatchCount);
  123. }
  124.